"""
给定图，问每条边是否可以存在于1到N的最短路上
1跑一个最短路，N跑一个最短路，对每条边判断一下即可
"""
import heapq
from typing import List, Union

class Graph(object):
    INF = 10 ** 10
    def __init__(self, N: int) -> None:
        self.N = N  # N个点，编号从1到N
        self.G = [[] for i in range(N + 1)]
        return
    def mkDiEdge(self, a: int, b: int, w) -> None:
        self.G[a].append((b, w))
    def mkBiEdge(self, a: int, b: int, w) -> None:
        self.mkDiEdge(a, b, w)
        self.mkDiEdge(b, a, w)
    def Dijkstra(self, src: int) -> List:
        """
        最短路，只能用在正边权上
        src: 起点
        return: 距离数组D, Pre，Di表示src到i的最短将距离
           Prei表示Prei到i是src到i的最短路的最后一条边
        """
        class T: # 嵌套类
            def __init__(self, node: int, w) -> None:
                self.node = node
                self.w = w
            def __lt__(self, other: 'T') -> bool:
                if self.w != other.w: return self.w < other.w
                return self.node < other.node
        Q = []  # 优先级队列
        D = [Graph.INF for i in range(self.N + 1)]
        D[src] = 0
        Pre = [0 for i in range(self.N + 1)]
        Flag = [False for i in range(self.N + 1)]
        heapq.heappush(Q, T(src, 0))
        while True:
            while len(Q) != 0:
                if not Flag[Q[0].node]:  # Q[0]就是最小的
                    break
                heapq.heappop(Q)
            if len(Q) == 0: break
            h = heapq.heappop(Q)
            Flag[h.node] = True
            for to, w in self.G[h.node]:
                if Flag[to]: continue
                tmp = D[h.node] + w
                if tmp < D[to]:
                    D[to] = tmp
                    Pre[to] = h.node
                    heapq.heappush(Q, T(to, tmp))
        return D, Pre


class Solution:
    def findAnswer(self, n: int, edges: List[List[int]]) -> List[bool]:
        M = len(edges)
        G = Graph(n)
        for a, b, c in edges:
            G.mkBiEdge(a + 1, b + 1, c)
        D1, _ = G.Dijkstra(1)
        ans = [False for i in range(M)]
        target = D1[G.N]
        if target == Graph.INF: return ans
        DN, _ = G.Dijkstra(G.N)
        for i in range(M):
            a, b, w = edges[i]
            a += 1
            b += 1
            if D1[a] + DN[b] + w == target or D1[b] + DN[a] + w == target: ans[i] = True
        return ans